package _05_stack.my_implements;

import _05_stack.AbstractStack;

import java.util.Iterator;

/**
 * @author: mornd
 * @dateTime: 2023/6/6 - 15:42
 * 基于链表实现
 * 添加节点类Node，该类中一个属性item保存存储的元素，另一个属性perv保存该节点的上一个
 * 一开始顶哨兵top指向底哨兵bottom，待push时，
 * 将新增元素e的prev指向top，再将e设置为顶哨兵，待下次push时，新元素的prev又会指向这里
 * 如果元素e的prev=bottom那么该栈就存储了这一个元素，且该元素就是栈顶
 */
public class LinkedListStack<E> extends AbstractStack<E> {

    /**
     * 已用大小
     */
    int size;

    /**
     * 顶部哨兵
     */
    Node<E> top = new Node(obj);

    static final Object obj = new Object();

    /**
     * 底部哨兵
     */
    Node<E> bottom = top;

    /**
     * 栈容量，超过该容量就不能添加元素
     */
    final int capacity;

    public LinkedListStack() {
        capacity = Integer.MAX_VALUE;
    }

    public LinkedListStack(int capacity) {
        this.capacity = capacity;
    }

    /*
        bottom                   top
        1       2     3     4
        b       t
            1   2
     */
    @Override
    public boolean push(E e) {
        if(isFull()) {
            return false;
        }
        top = new Node<>(e, top);
        size++;
        return true;
    }

    @Override
    public E pop() {
        if(isEmpty()) {
            return null;
        }
        Node<E> n = top;
        top = n.prev;
        size--;
        return n.item;
    }

    @Override
    public E peek() {
        if(isEmpty()) {
            return null;
        }
        return top.item;
    }

    @Override
    public boolean isEmpty() {
        return top == bottom;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = top;
            @Override
            public boolean hasNext() {
                return p != bottom;
            }

            @Override
            public E next() {
                E v = p.item;
                p = p.prev;
                return v;
            }
        };
    }

    /**
     * 链表节点
     * @param <E>
     */
    static class Node<E> {
        E item;
        Node<E> prev;

        public Node() {
        }

        public Node(E item) {
            this.item = item;
        }

        public Node(E item, Node<E> prev) {
            this.item = item;
            this.prev = prev;
        }
    }
}
